package org.lep.leetcode.datastructure.linkedlist.reverselinkedlist;

/**
 * Source : https://leetcode.com/problems/reverse-linked-list/
 *
 * Created by lverpeng on 2017/8/4.
 *
 * Reverse a singly linked list.
 *
 * click to show more hints.】
 *
 * Hint:
 * A linked list can be reversed either iteratively or recursively. Could you implement both?
 */
public class ReverseLinkedList {

    /**
     *
     * 反转单向链表
     *
     * 使用迭代的方法
     *
     * @param head
     * @return
     */
    public Node reverseByIterative (Node head) {
        Node pre = null;
        while (head != null) {
            Node next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;

    }

    /**
     * 使用递归
     *
     * @param head
     * @return
     */
    public Node reverseByRecursion (Node head, Node pre) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            head.next = pre;
            return head;
        }
        Node next = head.next;
        head.next = pre;
        pre = head;
        return reverseByRecursion(next, pre);
    }


    private static class Node {
        int value;
        Node next;

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", next=" + (next == null ? "" : next.value) +
                    '}';
        }
    }

    private static void print (Node node) {
        while (node != null) {
            System.out.println(node);
            node = node.next;
        }
        System.out.println();
    }

    public Node createList (int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        Node head = new Node();
        head.value = arr[0];
        Node pointer = head;
        for (int i = 1; i < arr.length; i++) {
            Node node = new Node();
            node.value = arr[i];
            pointer.next = node;
            pointer = pointer.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ReverseLinkedList reverseLinkedList = new ReverseLinkedList();

        print(reverseLinkedList.reverseByIterative(reverseLinkedList.createList(new int[]{1,2,3,4})));
        print(reverseLinkedList.reverseByIterative(reverseLinkedList.createList(new int[]{})));

        print(reverseLinkedList.reverseByRecursion(reverseLinkedList.createList(new int[]{1,2,3,4}), null));
        print(reverseLinkedList.reverseByRecursion(reverseLinkedList.createList(new int[]{}), null));
    }

}
